#include<iostream>
#include<stack>
using namespace std;
typedef struct tree {
    char data;
    struct tree* lchriden;
    struct tree*rchriden;
} tree,*bittree;
void treeinit(bittree &t){
    t->lchriden=NULL;
    t->rchriden=NULL;
}
bittree creattree() {
    char data;
    char tem;
    bittree t;
    cout<<"请输入数据，如果输入#则代表输入结束";
    cin>>data;
    tem=getchar();
    if(data=='#') {
        return NULL;
    }
    else {
        t=new tree;
        t->data=data;
        cout<<"开始输入左子树"<<endl;
        t->lchriden=creattree();
        cout<<"开始输入右子树"<<endl;
        t->rchriden=creattree();
        return t;
    }
}
void dfs(bittree t,int max1,int &maxvalue) {
    if(t==NULL) return;
    if(max1>maxvalue) {
        maxvalue=max1;
    }
    dfs(t->lchriden,max1+1,maxvalue);
    dfs(t->rchriden,max1+1,maxvalue);
}
void xianxv(bittree t) {
    if(t==NULL) return;
    cout<<t->data<<" ";
    xianxv(t->lchriden);
    xianxv(t->rchriden);
}
void zhongxv(bittree t) {
    if(t==NULL) return;
    zhongxv(t->lchriden);
    cout<<t->data<<" ";
    zhongxv(t->rchriden);
}
void houxv(bittree t) {
    if(t==NULL) return;
    houxv(t->lchriden);

    houxv(t->rchriden);
    cout<<t->data<<" ";
}
int geshu(bittree t) {
    if(t==NULL) {
        return 0;
    }
    return 1+geshu(t->lchriden)+geshu(t->rchriden);
}
void zhongxv_feidigui(bittree p) {
    if(p==NULL) return;
    stack<bittree> st;
    bittree q;
    while(p||!st.empty()) {
        if(p) {
            st.push(p);
            p=p->lchriden;
        }
        else {
            q=st.top();
            st.pop();
            cout<<q->data<<" ";
            p=q->rchriden;
        }
    }

}

int main()
{
    cout<<"开始创建树"<<endl;
    bittree t;
    cout<<"创建成功"<<endl;
    treeinit(t);
    cout<<"开始初始化树"<<endl;
    treeinit(t);
    cout<<"初始化成功"<<endl;
    cout<<"开始采用先序遍历输入树"<<endl;
    t=creattree();
    cout<<"输入成功"<<endl;
    int n;
    do{
      cout<<"请输入数字，1为先序遍历，2为中序遍历，3为后序遍历，4为中序遍历非递归版，0为输出结束";
      cin>>n;
      if(n<0||n>4){
        cout<<"输入错误，请重新输入"<<endl;
        continue;
      }
      if(n==1){
        cout<<"开始执行先序遍历"<<endl;
        xianxv(t);
      }  
      if(n==2){
        cout<<"开始执行中序遍历（递归）"<<endl;
        zhongxv(t);
      }
      if(n==3){
        cout<<"开始执行后序遍历"<<endl;
        houxv(t);
      }
      if(n==4){
        cout<<"开始执行中序遍历（递归）"<<endl;
         zhongxv_feidigui(t);
      }
    }while(n!=0);
    cout<<"遍历结束"<<endl;
    cout<<"开始求深度:";
    int max1=1,maxv=0;
    dfs(t,max1,maxv);
    cout<<maxv<<endl;
    cout<<"开始求个数:";
    cout<<geshu(t)<<endl;
    system("pause");
    return 0;
}
